package org.hmh.offer;

/**
 * Created this one by HMH on 2018/1/21.
 */
public class t28 {

    static public class Solution {
        public int InversePairs(int [] array) {
            mergeSort(array, 0, array.length-1);
            return result;
        }

        int result = 0;

        public void mergeSort(int[] arr, int l, int r){
            if(l<r){
                int mid = l + (r - l) / 2;
                mergeSort(arr, l, mid);
                mergeSort(arr, mid+1, r);
                mergeList(arr, l, r, mid);
            }
        }

        public void mergeList(int[] arr, int l, int r, int mid){
            int temp[] = new int[r - l +1];
            int i = l;
            int j = mid + 1;
            int count = 0;
            while( i <= mid || j <= r){
                if (i == mid + 1){
                    temp[count++] = arr[j++];
                }else if(j == r+1){
                    temp[count++] = arr[i++];
                }else if(arr[i]>arr[j]){
                    result += (mid-i)+1;
                    temp[count++] = arr[j++];
                }else{
                    temp[count++] = arr[i++];
                }
            }
            for (int k = 0 ; k < count ; k++){
                arr[k+l] = temp[k];
            }
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        int result = solution.InversePairs(new int[]{364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575});
        System.out.println(result);
    }
}
